<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    function Node (key) {
          this.key = key
          this.left = null
          this.right = null
        }
    class BinarySearchTree {
      constructor () {
        this.root = null
        this.traversal = []
      }
      // 1.插入节点函数
      insert (key) {
        const newNode = new Node(key)
        // 当没有根节点的时候
        if (!this.root) {
          this.root = newNode
          return true
        }
        // 有根节点的时候
        return this.insertNode(this.root, newNode)
      }
        // 1.1插入节点的递归函数
      insertNode (node, newNode) {
        if (newNode.key < node.key) {
          if (!node.left) {
            node.left = newNode
          } else {
            this.insertNode(node.left, newNode)
          }
        } else {
          if (!node.right) {
            node.right = newNode
          } else {
            this.insertNode(node.right, newNode)
          }
        }
        return true
      }
      // 2. 获取最小值
      min () {
        return this.getMinNode().node.key
      }
      getMinNode (node = this.root) {
        // 做了一些小改进方便后面删除元素得时候调用
        if (!node) return undefined
        // 保存他的父节点
        let parent = null
        while (node.left) {
          parent = node
          node = node.left
        }
        return { node, parent }
      }
      // 3. 获取最大值
      max (node = this.root) {
        return this.getMaxNode().key
      }
      getMaxNode (node = this.root) {
        let parent = null
        if (!node) return undefined
        while (node.right) {
          parent = node
          node = node.right
        }
        return { node, parent }
      }
      // 4. 搜索
      search (key) {
        let current = this.root
        while (current) {
          if (current.key > key) {
            current = current.left
          } else if (current.key < key) {
            current = current.right
          } else {
            return true
          }
        }
        return undefined
      }
      // 5. 删除节点
      remove (key) {
        let current = this.root
        let parent = null
        let isLeftChild = true
        // 判断是否为根节点
        // if (this.root.key === key) {
        //   this.root = null
        // }
        // 1. 寻找节点
        while (current.key !== key) {
          // 保存父节点
          parent = current
          if (key < current.key) {
            isLeftChild = true
            current = current.left
          } else {
            isLeftChild = false
            current = current.right
          }
          // 如果其中过程current指向了null则返回false
          if (!current) {
            console.log(111)
            return false
          }
        }
        // 2. 判断是什么节点
        // 2.1 叶子节点
        if (!current.left && !current.right) {
          // 是根节点的时候
          if (this.root === current) {
            this.root = null
          } else {
            isLeftChild ? (parent.left = null) : (parent.right = null)
          }
          // 2.2 只含有右节点
        } else if (!current.left) {
          // 2.2.1 是根节点的时候
          if (current === this.root) {
            this.root = this.root.right
          } else {
          // 2.2.2 判断是父亲得左节点还是右节点
            isLeftChild ? (parent.left = current.right) : (parent.right = current.right)
          }
          // 2.3 只含有左节点
        } else if (!current.right) {
            // 同上
          if (current === this.root) {
            this.root = this.root.left
          } else {
            isLeftChild ? (parent.left = current.left) : (parent.right = current.left)
          }
          // 2.4 含有左右节点时
        } else {
          // 有两种方法 
          // 一种是左节点的最大节点做根节点
          let { node: newRoot, parent: newRootParent } = this.getMaxNode(current.left)
          // 接触newRootParent的指引
          newRootParent.right = null
            // 根节点
          if (this.root === current) {
            this.root = newRoot
          } else {
            // 不是根节点
            if (isLeftChild) {
              parent.left = newRoot
            } else {
              parent.right = newRoot
            }
          }
          // 一种是右节点的最小节点做根节点
          // let newRoot = this.getMinNode(current.right)
          newRoot.left = current.left
          newRoot.right = current.right
        }
        // 删除成功
        return true
      }

      // 遍历方法
      // 先序遍历
      preOrderTraversal (handle) {
        this.traversal = []
        handle = handle || (key => {
          this.traversal.push(key)
        })
        this.preOrderTraversalNode(this.root, handle)
        if (this.root || !(this.traversal.length !== 0)) {
          return this.traversal.join(' -> ')
        }
      }
        // 先序遍历插入节点
      preOrderTraversalNode (node, handle) {
        if (node) {
          console.log(node)
          handle(node.key)
          // 遍历左节点
          this.preOrderTraversalNode(node.left, handle)
          // 遍历右节点
          this.preOrderTraversalNode(node.right, handle)
        }
      }
      // 中序遍历
      inOrderTraversal (handle) {
        this.traversal = []
        handle = handle || (function (key) {
          this.traversal.push(key)
        }.bind(this))
        this.inOrderTraversalNode(this.root, handle)
        if (this.root || !(this.traversal.length !== 0)) {
          return this.traversal.join(' -> ')
        }
      }
      inOrderTraversalNode (node, handle) {
        if (node) {
          this.inOrderTraversalNode(node.left, handle)
          handle(node.key)
          this.inOrderTraversalNode(node.right, handle)
        }
      }
      // 后续遍历
      postOrderTraversal (handle) {
        this.traversal = []
        handle = handle || (key => {
          this.traversal.push(key)
        })
        this.postOrderTraversalNode(this.root, handle)
        if (this.root || !(this.traversal.length !== 0)) {
          return this.traversal.join(' -> ')
        }
      }
      postOrderTraversalNode (node, handle) {
        if (node) {
          this.postOrderTraversalNode(node.left, handle)
          this.postOrderTraversalNode(node.right, handle)
          handle(node.key)
        }
      }
    }
    const test1 = new BinarySearchTree()
    test1.insert(11)
    test1.insert(7)
    test1.insert(15)
    test1.insert(5)
    test1.insert(3)
    test1.insert(9)
    test1.insert(8)
    test1.insert(10)
    test1.insert(13)
    test1.insert(12)
    test1.insert(14)
    test1.insert(20)
    test1.insert(18)
    // test1.insert(25)
    
    console.log(test1.inOrderTraversal())
    // console.log(test1.min())
    // console.log(test1.max())
    console.log(test1.remove(10))
    console.log(test1.search(3))
    console.log(test1.inOrderTraversal())
  </script>
</body>
</html>